// https://www.lintcode.com/problem/degree-of-an-array/

public class Solution {
    /**
     * @param nums: a list of integers
     * @return: return a integer
     */
    public int findShortestSubArray(int[] nums) {
        // write your code here
        int ret = nums.length;
        HashMap<Integer, Integer[]> map = new HashMap<>();
        List<Map.Entry<Integer, Integer[]>> candidates = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new Integer[]{0, i, i});
            }
            map.get(nums[i])[0] += 1;
            map.get(nums[i])[2] = i; // 出现次数，第一次和最近一次出现位置。
        }
        for (Map.Entry<Integer, Integer[]> entry : map.entrySet()) {
            Integer key = entry.getKey();
            Integer[] value = entry.getValue();
            if (candidates.size() == 0) {
                candidates.add(entry);
            } else {
                Map.Entry<Integer, Integer[]> last = candidates.get(candidates.size() - 1);
                if (value[0] > last.getValue()[0]) { // 前面全部清空
                    candidates.clear();
                    candidates.add(entry);
                } else if (value[0] == last.getValue()[0]) { // 相等则追加以后再判断
                    candidates.add(entry);
                }
            }
        }
        for (int i = 0; i < candidates.size(); ++i) {
            Map.Entry<Integer, Integer[]> candidate = candidates.get(i);
            int l = candidate.getValue()[2] - candidate.getValue()[1] + 1;
            if (l < ret) {
                ret = l;
            }
        }
        return ret;
    }
}